package com.itheima.leetcode.od.b.dynamicprogramming;

import java.util.Arrays;

/**
 * <h3>基站维护最短距离(换皮旅行商路径)</h3>
 * 小王是一名基站维护工程师，负责某区域的基站维护。某地方有n个基站(1 < n < 10)，已知各基站之间的距离 s(0 < s < 500) 并且基站到基站y的距离，与基站y到基站的距离并不一定会相同。小王从基站1出发，途经每个基站1次，然后返回基站1，需要请你为他选择一条距离最短的路。
 * <p>
 * 输入描述
 * <p>
 * 站点数n和各站点之间的距离(均为整数)。
 * 如:
 * 3{站点数}
 * 0 2 1 {站点1到各站点的路程]
 * 1 0 2 {站点2到各站点的路程]
 * 2 1 0 (站点3到各站点的路程
 * <p>
 * 输出描述
 * <p>
 * 最短路程的数值
 * <p>
 * 示例1：
 * <p>
 * 输入：
 * <p>
 * 3
 * 0 2 1
 * 1 0 2
 * 2 1 0
 * 输出：
 * <p>
 * 3
 */
public class MinimumDistanceForBaseStationMaintenance {
    public static void main(String[] args) {
        /*// 处理输入
        Scanner in = new Scanner(System.in);
        //转为数组
        int n = in.nextInt();
        int[][] matrix = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = in.nextInt();
            }
        }*/

        int n = 3;
        String input = "0 2 1\n1 0 2\n2 1 0";
        int[][] matrix = Arrays.stream(input.split("\n"))
                .map(s -> Arrays.stream(s.split(" "))
                        .mapToInt(Integer::parseInt)
                        .toArray())
                .toArray(int[][]::new);

        System.out.println(solve(n, matrix));
    }

    /**
     * 动态规划 + 状态压缩（不假设启点版本）
     *
     * @param n
     * @param matrix
     * @return
     */
    public static int solve(int n, int[][] matrix) {
        int MAX = 1 << n - 1;
        int[][] dp = new int[n][MAX];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < MAX; j++) {
                dp[i][j] = n * 500;
            }
        }
        for (int i = 0; i < n; i++) {
            dp[i][0] = matrix[i][0];
        }

        // j为当前状态
        for (int j = 0; j < MAX; j++) {
            // i为当前基站
            for (int i = 0; i < n; i++) {
                if (contains(j, i)) {
                    continue;
                }
                // k为下一个基站
                for (int k = 0; k < n; k++) {
                    if (contains(j, k)) {
                        dp[i][j] = Math.min(dp[i][j], dp[k][exclude(j, k)] + matrix[i][k]);
                    }
                }
            }
        }

        return dp[0][MAX - 1];
    }

    static int exclude(int set, int city) {
        return set ^ (1 << (city - 1));
    }

    static boolean contains(int set, int city) {
        if (0 == city) {
            return false;
        }
        return (set >> (city - 1) & 1) == 1;
    }
}